#pragma once

namespace Melting
{
// TODO : create a custom project for memory management code !

#define		ROUND_UP(_value,_align)		( _value + ( _align - 1 ) & (~( _align - 1) ) )
#define		IS_POWER_OF_TWO(_value)		( 0 == (_value & (_value-1) ) )


inline UBYTE* AlignedMalloc( UINT32 _iBlockSize, UINT32 _iAlignment )
{
	UBYTE* pMemory = (UBYTE*) malloc( _iBlockSize + _iAlignment );

	UBYTE* pAlignedMemory = (UBYTE*)((UINT32)( pMemory + _iAlignment ) & ( ~ (_iAlignment - 1 ) ));

	// safe, because adding _iAlignment instead of (_iAlignment-1) guarantees it is past the actual start of the maloc'ed block.
	*(pAlignedMemory - 1) = pAlignedMemory - pMemory;

	return pAlignedMemory;
}

inline void AlignedFree( UBYTE* _pAlignedMemory )
{
	UBYTE iOffset = *(_pAlignedMemory - 1);
	free( (void*)(_pAlignedMemory - iOffset) );
}

/// Return the position of the least significant bit of the given _iBitSet integer -- WARNING : passing 0 is forbidden !
inline INT32 FindLSB( UINT32 _iBitField )
{
#if WIN32
	DWORD iLSB;
	_BitScanForward( &iLSB, _iBitField );
	return iLSB;
#elif _GCC
	return __builtin_ctz( _iBitField );
#else
	// taken from : http://graphics.stanford.edu/~seander/bithacks.html
	static const UINT32 MultiplyDeBruijnBitPosition[32] = 
	{
	  0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8, 
	  31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9
	};
	return MultiplyDeBruijnBitPosition[((UINT32)((_iBitField & -_iBitField) * 0x077CB531U)) >> 27];
#endif 
}

/// Return the position of the most significant bit of the given _iBitSet integer -- WARNING : passing 0 is forbidden !
inline INT32 FindMSB( UINT32 _iBitField )
{
#if WIN32
	DWORD iLSB;
	_BitScanReverse( &iLSB, _iBitField );
	return iLSB;
#elif _GCC
	return __builtin_clz( _iBitField );
#else
	// taken from : http://graphics.stanford.edu/~seander/bithacks.html 
	static const int MultiplyDeBruijnBitPosition[32] = 
	{
	  0, 9, 1, 10, 13, 21, 2, 29, 11, 14, 16, 18, 22, 25, 3, 30,
	  8, 12, 20, 28, 15, 17, 24, 7, 19, 27, 23, 6, 26, 5, 4, 31
	};

	_iBitField |= _iBitField >> 1; // first round down to one less than a power of 2 
	_iBitField |= _iBitField >> 2;
	_iBitField |= _iBitField >> 4;
	_iBitField |= _iBitField >> 8;
	_iBitField |= _iBitField >> 16;

	return MultiplyDeBruijnBitPosition[(UINT32)(_iBitField * 0x07C4ACDDU) >> 27];

#endif  
}
//
///// Return the position of the least significant bit of the given _iBitSet integer -- WARNING : passing 0 is forbidden !
//inline UINT64 FindLSB64( UINT64 _iBitField )
//{
//#if WIN32
//	DWORD iLSB;
//	_BitScanForward64( &iLSB, _iBitField );
//	return iLSB;
//#elif _GCC
//	return __builtin_ctzll( _iBitField );
//#else
//	// taken from : http://graphics.stanford.edu/~seander/bithacks.html
//	static const UINT32 MultiplyDeBruijnBitPosition[32] = 
//	{
//	  0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8, 
//	  31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9
//	};
//	return MultiplyDeBruijnBitPosition[((UINT32)((_iBitField & -_iBitField) * 0x077CB531U)) >> 27];
//#endif 
//}
//
///// Return the position of the most significant bit of the given _iBitSet integer -- WARNING : passing 0 is forbidden !
//inline UINT64 FindMSB64( UINT64 _iBitField )
//{
//#if WIN32
//	DWORD iLSB;
//	_BitScanReverse64( &iLSB, _iBitField );
//	return iLSB;
//#elif _GCC
//	return __builtin_clzll( _iBitField );
//#else
//	// taken from : http://graphics.stanford.edu/~seander/bithacks.html 
//	static const int MultiplyDeBruijnBitPosition[32] = 
//	{
//	  0, 9, 1, 10, 13, 21, 2, 29, 11, 14, 16, 18, 22, 25, 3, 30,
//	  8, 12, 20, 28, 15, 17, 24, 7, 19, 27, 23, 6, 26, 5, 4, 31
//	};
//
//	_iBitField |= _iBitField >> 1; // first round down to one less than a power of 2 
//	_iBitField |= _iBitField >> 2;
//	_iBitField |= _iBitField >> 4;
//	_iBitField |= _iBitField >> 8;
//	_iBitField |= _iBitField >> 16;
//
//	return MultiplyDeBruijnBitPosition[(UINT32)(_iBitField * 0x07C4ACDDU) >> 27];
//
//#endif  
//}



inline void UnitTest_FindLSB()
{ 
	INT32 i;

	i = FindLSB( 1 );		
	MB_ASSERT( 0 == i , "FindLSB is broken" );

	i = FindLSB( 3 );		
	MB_ASSERT( 0 == i , "FindLSB is broken" );

	i = FindLSB( 2 );		
	MB_ASSERT( 1 == i , "FindLSB is broken" );

	i = FindLSB( 4 );		
	MB_ASSERT( 2 == i , "FindLSB is broken" );

	i = FindLSB( 5 );		
	MB_ASSERT( 0 == i , "FindLSB is broken" );

	i = FindLSB( 16 );		
	MB_ASSERT( 4 == i , "FindLSB is broken" );

	i = FindLSB( 32 );		
	MB_ASSERT( 5 == i , "FindLSB is broken" );

	i = FindLSB( 33 );		
	MB_ASSERT( 0 == i , "FindLSB is broken" );
} 

inline void UnitTest_FindMSB()
{ 
	INT32 i;

	i = FindMSB( 1 );		
	MB_ASSERT( 0 == i , "FindMSB is broken" );

	i = FindMSB( 3 );		
	MB_ASSERT( 1 == i , "FindMSB is broken" );

	i = FindMSB( 2 );		
	MB_ASSERT( 1 == i , "FindMSB is broken" );

	i = FindMSB( 4 );		
	MB_ASSERT( 2 == i , "FindMSB is broken" );

	i = FindMSB( 5 );		
	MB_ASSERT( 2 == i , "FindMSB is broken" );

	i = FindMSB( 16 );		
	MB_ASSERT( 4 == i , "FindMSB is broken" );

	i = FindMSB( 32 );		
	MB_ASSERT( 5 == i , "FindMSB is broken" );

	i = FindMSB( 33 );		
	MB_ASSERT( 5 == i , "FindMSB is broken" );
} 


 

/// Hierarchical BitFields Indexed Memory Pool - constant time for alloc & free
class HBFIMemoryPool
{
public:

	/// MAX BlockCount is 2^30! - cause going up to 2^32 would be a waste !
	HBFIMemoryPool	( void )
	:	miBlockSize			( 0 )	// re compute later 
	,	miBlockCount		( 0 )	
	,	miInfoCount			( 0 )			// compute later  
	,	miCurrentAllocCount	( 0 )
	,	miTotalAllocCount	( 0 )
	,	maInfos				( nullptr ) 
	{		
	}

	~HBFIMemoryPool	( void )
	{
		if( nullptr != maInfos )
		{
			Release();
		}
	} 
	//--------------------------------------------------------------------------------------------------------------------
	//--------------------------------------------------------------------------------------------------------------------
	void Initialize( UINT32 _iBlockSize, UINT32 _iMinBlocks, UINT32 _iBlockAlignment )
	{
		//--------------------
		// precondition
		MB_ASSERT( 0 == _iBlockAlignment || IS_POWER_OF_TWO( _iBlockAlignment ), "Invalid block alignment value\n" );
		MB_ASSERT( 0 < _iMinBlocks , "Cannot create a pool for 0 blocks...\n" );
		//-------------------- 

		miBlockSize			= _iBlockSize;	// re compute later 
		miBlockCount		= _iMinBlocks;	
		miInfoCount			= 0;			// compute later  
		miCurrentAllocCount	= 0;
		miTotalAllocCount	= 0;


		// if block alignment is requested, proceed by modifying the requested 
		if( 0 != _iBlockAlignment )
		{
			miBlockSize = ROUND_UP( _iBlockSize, _iBlockAlignment );
		} 

		UINT32 iMSB = FindMSB( miBlockCount );
		UINT32 iLSB = FindLSB( miBlockCount );

		// round up the MSB if it is not exactly a power of 2
		UINT32 iRoundedUpMSB = ( iMSB != iLSB )? iMSB + 1 : iMSB;

		// Nb levels in the hierarchy - each level can manage 32 sublevels, one per bit, so ...
		miNbLevels = iRoundedUpMSB / 5; // 5 because 2^5 = 32, and an UINT32 has 32 bits

		// Round up for the remaining bits that disappeared in the div
		miNbLevels = ( iRoundedUpMSB % 5 ) ? miNbLevels + 1: miNbLevels ;

		// Could be shared, but for potentially faster access, I prefer have 1 per object
		maLevelInfos[ 0 ].miOffset		= 0;
		maLevelInfos[ 0 ].miNbBitFields = 1;

		UINT32 iTotalNbBitFields = maLevelInfos[ 0 ].miNbBitFields;

		for( UINT32 i = 1; i < miNbLevels; i++ )
		{
			maLevelInfos[ i ].miOffset		= maLevelInfos[ i - 1 ].miOffset + maLevelInfos[ i - 1 ].miNbBitFields; //* sizeof(UINT32);
			maLevelInfos[ i ].miNbBitFields	= maLevelInfos[ i - 1 ].miNbBitFields * 32;

			iTotalNbBitFields	+= maLevelInfos[ i ].miNbBitFields;
		}
		
		// compute the number of required UINT32 to index all blocks
		miInfoCount = iTotalNbBitFields; /// 32 ;

		// Compute the global alignment, taking into consideration the block alignment requested and the default 16 bytes aligment 
		// for the Start of the 'blocks' 
		UINT32 iAlignment = max( 16, ROUND_UP(_iBlockAlignment, 16 ) );

		// Round Up to make sure the concatenated block will have both the first 'info' part 
		// and the next 'blocks' part aligned on the defined	iAlignment
		UINT32 iInfoChunkSize	=  ROUND_UP( sizeof(UINT32) * miInfoCount, iAlignment );
		UINT32 iBlocksChunkSize = miBlockCount * _iBlockSize;

		UBYTE* pMemory	= AlignedMalloc( iInfoChunkSize + iBlocksChunkSize, iAlignment );

		// share the unique buffer between the 2 arrays, 'infos' & 'blocks'
		maInfos		= (UINT32*)pMemory;
		maBlocks	= pMemory + iInfoChunkSize;

		// init the info table 
		for( UINT32 i = 0; i < miInfoCount; i++ )
		{
			maInfos[ i ] = 0xFFFFFFFF;
		}
	}
	//--------------------------------------------------------------------------------------------------------------------
	//--------------------------------------------------------------------------------------------------------------------
	void Release( void )
	{	
		//--------------------
		// precondition
		MB_ASSERT( nullptr != maInfos, "MemoryPool already Release(), or not properly Initialize()...\n" );
		//-------------------- 

		// will delete the whole chunk shared between 'info' & 'blocks'
		AlignedFree( (UBYTE*)maInfos );
		maInfos = nullptr;
	}
	//--------------------------------------------------------------------------------------------------------------------
	//--------------------------------------------------------------------------------------------------------------------
	UBYTE*		Allocate( void )
	{ 
		MB_ASSERT( 0 != maInfos[ 0 ], "Memory Pool is too small\n" ); 

 
		const UINT32 FULL = 0; 
  
		UBYTE	aJumpLevels[ 8 ]	= { 0, 0, 0, 0, 0, 0, 0, 0 };
		UINT32*	apBitFields[ 8 ]	= { 0, 0, 0, 0, 0, 0, 0, 0 }; 

		UINT32 iLevelSlot = 0;
		UINT32 iNewBitField;

		for( UINT32 i = 0; i < miNbLevels; i++ )
		{			
			iLevelSlot = 0;
			for( UINT j = 0; j < i ; j++ )
			{
				iLevelSlot += aJumpLevels[ j ] * maLevelInfos[ i - (1+j) ].miNbBitFields;
			}

			apBitFields[ i ]	= & maInfos[ maLevelInfos[ i ].miOffset + iLevelSlot ];

			// get the jump offset for this level
			UINT32 iBitField	= *apBitFields[ i ];
			UINT32 iLSB			= FindLSB( iBitField );
			aJumpLevels[ i ]	= iLSB;

			iNewBitField	= iBitField & ~( 1 << iLSB );
		}

		// finally set the bit to 0 !
		*apBitFields[ miNbLevels - 1 ] = iNewBitField;

		// update the parent bitfields in the hierachy, each time we have a full bit fields
		for( UINT32 i = miNbLevels - 1; i > 0; i-- )
		{	
			// if level bit field is FULL, notify its bitfield parent
			if( 0 == *apBitFields[ i ] )
			{
				*apBitFields[ i - 1 ] = *apBitFields[ i - 1 ] & ~( 1 << aJumpLevels[ i - 1 ] );
			}	
			else
			{
				break;
			}
		}

		// useful info 
		miCurrentAllocCount++;
		miTotalAllocCount++;

		// find Block index from jump offsets
		// NB : we already computed it with the last iLevelSlot
		UINT32 iBlockIndex = aJumpLevels[ miNbLevels - 1 ] + iLevelSlot * 32 ; 

		return & maBlocks[ iBlockIndex * miBlockSize ]; 
	}

	//--------------------------------------------------------------------------------------------------------------------
	//--------------------------------------------------------------------------------------------------------------------
	void		Free( UBYTE* _pBlock )
	{
		// compute its index from its address
		UINT32 iIndex = static_cast<UINT32>( _pBlock - maBlocks ) / miBlockSize;

		for( UINT32 i = 0; i < miNbLevels; i++ )
		{
			// compute slot id & bit position from its index
			UINT32 iSlot	= iIndex / 32;
			UINT32 iBit		= iIndex % 32;
			
			// previous and new bitsets
			UINT32 iOffset		= maLevelInfos[ miNbLevels - 1 - i].miOffset;
			UINT32 iInfoIdx		= iSlot + iOffset;
			UINT32 iBitField	= maInfos[ iInfoIdx ];
			UINT32 iNewBitField	= iBitField | ( 1 << iBit );  

			// release the index 
			maInfos[ iInfoIdx ] = iNewBitField;

			// if the bitfield WAS full, it is now more, so we must update its parent
			if( 0 == iBitField )
			{
				iIndex /= 32;
			}
			else
			{
				break;
			}
		} 
		 
		// useful info 
		miCurrentAllocCount--;
	}
 	//--------------------------------------------------------------------------------------------------------------------
	//--------------------------------------------------------------------------------------------------------------------
	UINT32		GetTotalAllocationsCount( void ) const
	{
		return miTotalAllocCount;
	}

	//--------------------------------------------------------------------------------------------------------------------
	//--------------------------------------------------------------------------------------------------------------------
	UINT32		GetAllocationsCount( void ) const
	{
		return miCurrentAllocCount;
	}
 
	//--------------------------------------------------------------------------------------------------------------------
	//--------------------------------------------------------------------------------------------------------------------
	void PolluteEvenIndices()
	{
		UINT32 dirtyMask = 0xFFFFFFFF;

		for( UINT32 i = 0; i < 32; i+=2 )
		{
			dirtyMask = dirtyMask & ~( 1 << i );
		}

		
		UINT32 iOffset		= maLevelInfos[ miNbLevels - 1 ].miOffset;
		UINT32* apBitField	= & maInfos[ iOffset ];

		for( UINT32 i = 0; i < maLevelInfos[ miNbLevels - 1 ].miNbBitFields; i++ )
		{
			apBitField[ i ] = dirtyMask;
		}
		
		miCurrentAllocCount = miBlockCount/2;
		miTotalAllocCount = miBlockCount/2; 
	}

private:
	
	struct HierarchyLevelInfo
	{
		UINT32 miOffset;
		UINT32 miNbBitFields;
	};

	UINT32							miBlockSize;
	UINT32							miBlockCount;
	UINT32							miInfoCount; 
	UINT32							miCurrentAllocCount;
	UINT32							miTotalAllocCount; 

	UINT32							miNbLevels;
	HierarchyLevelInfo				maLevelInfos[8];

	UINT32*							maInfos;
	UBYTE*							maBlocks; 
};



class MemoryPool
{
public:

	MemoryPool	( void )
	:	miBlockSize			( 0 )	// re compute later 
	,	miBlockCount		( 0 )	
	,	miInfoCount			( 0 )			// compute later 
	,	miCandidateFreeSlot	( 0 )
	,	miCurrentAllocCount	( 0 )
	,	miTotalAllocCount	( 0 )
	,	maInfos				( nullptr )
	{ 
	}

	~MemoryPool	( void )
	{
		if( nullptr != maInfos )
		{
			Release();
		}
	} 
 
	//--------------------------------------------------------------------------------------------------------------------
	//--------------------------------------------------------------------------------------------------------------------
	void Initialize( UINT32 _iBlockSize, UINT32 _iMinBlocks, UINT32 _iBlockAlignment )
	{
		//--------------------
		// precondition
		MB_ASSERT( 0 == _iBlockAlignment || IS_POWER_OF_TWO( _iBlockAlignment ), "Invalid block alignment value\n" );
		MB_ASSERT( 0 < _iMinBlocks , "Cannot create a pool for 0 blocks...\n" );
		//-------------------- 


		miBlockSize			= _iBlockSize;	// re compute later 
		miBlockCount		= _iMinBlocks;	
		miInfoCount			= 0;			// compute later 
		miCandidateFreeSlot	= 0;
		miCurrentAllocCount	= 0;
		miTotalAllocCount	= 0;


		// if block alignment is requested, proceed by modifying the requested 
		if( 0 != _iBlockAlignment )
		{
			miBlockSize = ROUND_UP( _iBlockSize, _iBlockAlignment );
		}
		// compute the number of required UINT32 to index all blocks
		miInfoCount = 1 + miBlockCount / 32;

		// Compute the global alignment, taking into consideration the block alignment requested and the default 16 bytes aligment 
		// for the Start of the 'blocks' 
		UINT32 iAlignment = max( 16, ROUND_UP(_iBlockAlignment, 16 ) );

		// Round Up to make sure the concatenated block will have both the first 'info' part 
		// and the next 'blocks' part aligned on the defined	iAlignment
		UINT32 iInfoChunkSize	=  ROUND_UP( sizeof(UINT32) * miInfoCount, iAlignment );
		UINT32 iBlocksChunkSize = miBlockCount * _iBlockSize;

		UBYTE* pMemory	= AlignedMalloc( iInfoChunkSize + iBlocksChunkSize, iAlignment );

		// share the unique buffer between the 2 arrays, 'infos' & 'blocks'
		maInfos		= (UINT32*)pMemory;
		maBlocks	= pMemory + iInfoChunkSize;

		// init the info table 
		for( UINT32 i = 0; i < miInfoCount; i++ )
		{
			maInfos[ i ] = 0xFFFFFFFF;
		}
	}
	//--------------------------------------------------------------------------------------------------------------------
	//--------------------------------------------------------------------------------------------------------------------
	void Release( void )
	{	
		//--------------------
		// precondition
		MB_ASSERT( nullptr != maInfos, "MemoryPool already Release(), or not properly Initialize()...\n" );
		//-------------------- 

		// will delete the whole chunk shared between 'info' & 'blocks'
		AlignedFree( (UBYTE*)maInfos );
		maInfos = nullptr;
	}
	
	//--------------------------------------------------------------------------------------------------------------------
	//--------------------------------------------------------------------------------------------------------------------
	UBYTE*		Allocate( void )
	{
		UINT32 iFound = 0xFFFFFFFF;
		
		const UINT32 FULL = 0;

		UINT32 iInfoCount = miInfoCount;
		UINT32 iCandidate = miCandidateFreeSlot;
 
		UINT32 i = iCandidate; 

		while( i < iInfoCount + iCandidate )
		{
			// stay in the bounds!
			int iSlot = i % iInfoCount;

			UINT32 iFreeBits = maInfos[ iSlot ];

			// if some bits are free ...
			if( FULL != iFreeBits )
			{
				// find the first least significant bit set to 1 
				UINT32 iLSB = FindLSB( iFreeBits );

				// and flip it to 0, to say "I'm using it"
				UINT32 iNewFreeBits = iFreeBits & ~( 1 << iLSB );

				// TODO : in multi thread env, lock only when trying to take it!

				// take it 
				maInfos[ iSlot ] = iNewFreeBits;

				// try to update the candidate slot index 
				if( FULL == iNewFreeBits )
				{
					miCandidateFreeSlot	= ( miCandidateFreeSlot + 1 ) % iInfoCount;
				}

				// useful info 
				miCurrentAllocCount++;
				miTotalAllocCount++;

				// okaaayy !!!
				iFound = iSlot * 32 + iLSB;

				break; 
			}
			// else retry with next 32bits !
			i++;
		}
 
		MB_ASSERT( 0xFFFFFFFF != iFound, "Memory Pool is too small\n" ); 

		return & maBlocks[ iFound * miBlockSize ];

	}

	//--------------------------------------------------------------------------------------------------------------------
	//--------------------------------------------------------------------------------------------------------------------
	void		Free( UBYTE* _pBlock )
	{
		// compute its index from its address
		UINT32 iIndex = static_cast<UINT32>( _pBlock - maBlocks ) / miBlockSize;

		// compute slot id & bit position from its index
		UINT32 iSlot	= iIndex / 32;
		UINT32 iBit		= iIndex % 32;

		// previous and new bitsets
		UINT32 iBitSet		= maInfos[ iSlot ];
		UINT32 iNewBitSet	= iBitSet | ( 1 << iBit );  

		// release the index 
		maInfos[ iSlot ] = iNewBitSet;
		 
		// useful info 
		miCurrentAllocCount--;
	}
 
	//--------------------------------------------------------------------------------------------------------------------
	//--------------------------------------------------------------------------------------------------------------------
	UINT32		GetTotalAllocationsCount( void ) const
	{
		return miTotalAllocCount;
	}

	//--------------------------------------------------------------------------------------------------------------------
	//--------------------------------------------------------------------------------------------------------------------
	UINT32		GetAllocationsCount( void ) const
	{
		return miCurrentAllocCount;
	}
 
	//--------------------------------------------------------------------------------------------------------------------
	//--------------------------------------------------------------------------------------------------------------------
	void PolluteEvenIndices()
	{
		UINT32 dirtyMask = 0xFFFFFFFF;

		for( UINT32 i = 0; i < 32; i+=2 )
		{
			dirtyMask = dirtyMask & ~( 1 << i );
		}

		for( UINT32 i = 0; i < miInfoCount; i++ )
		{
			maInfos[ i ] = dirtyMask;
		}
		
		miCurrentAllocCount = miBlockCount/2;
		miTotalAllocCount = miBlockCount/2; 
	}

private:
	UINT32							miBlockSize;
	UINT32							miBlockCount;
	UINT32							miInfoCount;
	UINT32							miCandidateFreeSlot;
	UINT32							miCurrentAllocCount;
	UINT32							miTotalAllocCount; 

	UINT32*							maInfos;
	UBYTE*							maBlocks; 
};


class NaiveMemoryPool
{
public:

	NaiveMemoryPool	( void )
	:	miBlockSize			( 0 )	// re compute later 
	,	miBlockCount		( 0 )	
	,	miInfoCount			( 0 )			// compute later 
	,	miCandidateFreeSlot	( 0 )
	,	miCurrentAllocCount	( 0 )
	,	miTotalAllocCount	( 0 )
	,	maInfos				( nullptr )
	{
	}

	~NaiveMemoryPool	( void )
	{
		if( nullptr != maInfos )
		{
			Release();
		}
	}
 
	//--------------------------------------------------------------------------------------------------------------------
	//--------------------------------------------------------------------------------------------------------------------
	void Initialize( UINT32 _iBlockSize, UINT32 _iMinBlocks, UINT32 _iBlockAlignment )
	{
		//--------------------
		// precondition
		MB_ASSERT( 0 == _iBlockAlignment || IS_POWER_OF_TWO( _iBlockAlignment ), "Invalid block alignment value\n" );
		MB_ASSERT( 0 < _iMinBlocks , "Cannot create a pool for 0 blocks...\n" );
		//-------------------- 


		miBlockSize			= _iBlockSize;	// re compute later 
		miBlockCount		= _iMinBlocks;	
		miInfoCount			= 0;			// compute later 
		miCandidateFreeSlot	= 0;
		miCurrentAllocCount	= 0;
		miTotalAllocCount	= 0;


		// if block alignment is requested, proceed by modifying the requested 
		if( 0 != _iBlockAlignment )
		{
			miBlockSize = ROUND_UP( _iBlockSize, _iBlockAlignment );
		}
		// compute the number of required UINT32 to index all blocks
		miInfoCount = miBlockCount;

		// Compute the global alignment, taking into consideration the block alignment requested and the default 16 bytes aligment 
		// for the Start of the 'blocks' 
		UINT32 iAlignment = max( 16, ROUND_UP(_iBlockAlignment, 16 ) );

		// Round Up to make sure the concatenated block will have both the first 'info' part 
		// and the next 'blocks' part aligned on the defined	iAlignment
		UINT32 iInfoChunkSize	=  ROUND_UP( sizeof(UINT32) * miInfoCount, iAlignment );
		UINT32 iBlocksChunkSize = miBlockCount * _iBlockSize;

		UBYTE* pMemory	= AlignedMalloc( iInfoChunkSize + iBlocksChunkSize, iAlignment );

		// share the unique buffer between the 2 arrays, 'infos' & 'blocks'
		maInfos		= (UINT32*)pMemory;
		maBlocks	= pMemory + iInfoChunkSize;

		// init the info table 	
		for( UINT32 i = 0; i < miInfoCount; i++ )
		{
			maInfos[ i ] = 1;
		}
	}
	//--------------------------------------------------------------------------------------------------------------------
	//--------------------------------------------------------------------------------------------------------------------
	void Release( void )
	{	
		//--------------------
		// precondition
		MB_ASSERT( nullptr != maInfos, "MemoryPool already Release(), or not properly Initialize()...\n" );
		//-------------------- 

		// will delete the whole chunk shared between 'info' & 'blocks'
		AlignedFree( (UBYTE*)maInfos );
		maInfos = nullptr;
	}
	
	//--------------------------------------------------------------------------------------------------------------------
	//--------------------------------------------------------------------------------------------------------------------
	UBYTE*		Allocate( void )
	{
		UINT32 iFound = 0xFFFFFFFF;
		
		const UINT32 FULL = 0;

		UINT32 iTry = 0;

		UINT32 iBlockCount = miBlockCount;

		while( iTry < iBlockCount )
		{
			// Use the "next" free slot as a candidate
			UINT32 iCandidate = miCandidateFreeSlot % iBlockCount;
			miCandidateFreeSlot++;

			UINT32 iFree = maInfos[ iCandidate ];

			if( FULL != iFree )
			{  
				// take it 
				maInfos[ iCandidate ] = 0;

				// useful info 
				miCurrentAllocCount++;
				miTotalAllocCount++;

				// okaaayy
				iFound = iCandidate;

				break; 
			}
			iTry++;
		}


		//UINT32 iInfoCount = miInfoCount;
		//UINT32 iCandidate = miCandidateFreeSlot;
 
		//UINT32 i = iCandidate; 

		//while( i < iInfoCount + iCandidate )
		//{
		//	// stay in the bounds!
		//	int iSlot = i % iInfoCount;

		//	UINT32 iFreeBits = maInfos[ iSlot ];

		//	// if it is free ...
		//	if( FULL != iFreeBits )
		//	{
		//		// TODO : in multi thread env, lock only when trying to take it!

		//		// take it 
		//		maInfos[ iSlot ] = 0;

		//		// try to update the candidate slot index 
		//		miCandidateFreeSlot	= ( miCandidateFreeSlot + 1 ) % iInfoCount; 

		//		// useful info 
		//		miCurrentAllocCount++;
		//		miTotalAllocCount++;

		//		// okaaayy !!!
		//		iFound = iSlot;

		//		break; 
		//	}
		//	// else retry with next 32bits !
		//	i++;
		//}
 
		MB_ASSERT( 0xFFFFFFFF != iFound, "Memory Pool is too small\n" ); 

		return & maBlocks[ iFound * miBlockSize ];
	}

	//--------------------------------------------------------------------------------------------------------------------
	//--------------------------------------------------------------------------------------------------------------------
	void		Free( UBYTE* _pBlock )
	{
		// compute its index from its address
		UINT32 iIndex = static_cast<UINT32>( _pBlock - maBlocks ) / miBlockSize;

		// release the index 
		maInfos[ iIndex ] = 1;
		 
		// useful info 
		miCurrentAllocCount--;
	}
 
	//--------------------------------------------------------------------------------------------------------------------
	//--------------------------------------------------------------------------------------------------------------------
	UINT32		GetTotalAllocationsCount( void ) const
	{
		return miTotalAllocCount;
	}

	//--------------------------------------------------------------------------------------------------------------------
	//--------------------------------------------------------------------------------------------------------------------
	UINT32		GetAllocationsCount( void ) const
	{
		return miCurrentAllocCount;
	}

	//--------------------------------------------------------------------------------------------------------------------
	//--------------------------------------------------------------------------------------------------------------------
	void PolluteEvenIndices()
	{
		for( UINT32 i = 0; i < miInfoCount; i+=2 )
		{
			maInfos[ i ] = 0;
		}
		miCurrentAllocCount = miBlockCount/2;
		miTotalAllocCount = miBlockCount/2; 
	}

private:
	UINT32							miBlockSize;
	UINT32							miBlockCount;
	UINT32							miInfoCount;
	UINT32							miCandidateFreeSlot;
	UINT32							miCurrentAllocCount;
	UINT32							miTotalAllocCount; 

	UINT32*							maInfos;
	UBYTE*							maBlocks; 
};




class LockFreeMemoryPool
{
public:


	LockFreeMemoryPool	( void )
	:	miBlockSize			( 0 )
	,	miBlockCount		( 0 )
	,	miCandidateFreeSlot	( 0 )
	,	miCurrentAllocCount	( 0 )
	,	miTotalAllocCount	( 0 )
	,	maInfos				( nullptr )
	{ 
	}

	~LockFreeMemoryPool	( void )
	{
		if( nullptr != maInfos )
		{
			Release();
		}
	}

	
	//--------------------------------------------------------------------------------------------------------------------
	//--------------------------------------------------------------------------------------------------------------------
	void LockFreeMemoryPool::Initialize( UINT32 _iBlockSize, UINT32 _iMinBlocks, UINT32 _iBlockAlignment )
	{
		//--------------------
		// precondition
		MB_ASSERT( 0 == _iBlockAlignment || IS_POWER_OF_TWO( _iBlockAlignment ), "Invalid block alignment value\n" );
		MB_ASSERT( 0 < _iMinBlocks , "Cannot create a pool for 0 blocks...\n" );
		//-------------------- 


		miBlockSize			= _iBlockSize;
		miBlockCount		= _iMinBlocks;
		miCandidateFreeSlot	= 0;
		miCurrentAllocCount	= 0;
		miTotalAllocCount	= 0;


		// if block alignment is requested, proceed by modifying the requested 
		if( 0 != _iBlockAlignment )
		{
			miBlockSize = ROUND_UP( _iBlockSize, _iBlockAlignment );
		}

		// Compute the global alignment, taking into consideration the block alignment requested and the default 16 bytes aligment 
		// for the Start of the 'blocks' 
		UINT32 iAlignment = max( 16, ROUND_UP(_iBlockAlignment, 16 ) );

		// Round Up to make sure the concatenated block will have both the first 'info' part 
		// and the next 'blocks' part aligned on the defined	iAlignment
		UINT32 iInfoChunkSize	=  ROUND_UP( sizeof(UINT32) * miBlockCount, iAlignment );
		UINT32 iBlocksChunkSize = miBlockCount * _iBlockSize;

		UBYTE* pMemory	= AlignedMalloc( iInfoChunkSize + iBlocksChunkSize, iAlignment );

		// share the unique buffer between the 2 arrays, 'infos' & 'blocks'
		maInfos		= (UINT32*)pMemory;
		maBlocks	= pMemory + iInfoChunkSize;

		// init the info table 	
		for( UINT32 i = 0; i < miBlockCount; i++ )
		{
			maInfos[ i ] = 1;
		}
	}

	//--------------------------------------------------------------------------------------------------------------------
	//--------------------------------------------------------------------------------------------------------------------
	void Release( void )
	{
		//--------------------
		// precondition
		MB_ASSERT( nullptr != maInfos, "MemoryPool already Release(), or not properly Initialize()...\n" );
		//-------------------- 

		// will delete the whole chunk shared between 'info' & 'blocks'
		AlignedFree( (UBYTE*)maInfos );
		maInfos = nullptr;
	}

	//--------------------------------------------------------------------------------------------------------------------
	//--------------------------------------------------------------------------------------------------------------------
	UBYTE*		Allocate( void )
	{
		UINT32 iFound = 0xFFFFFFFF;
		
		UINT32 iTry = 0;

		UINT32 iBlockCount = miBlockCount;

		while( iTry < iBlockCount )
		{
			// Use the "next" free slot as a candidate
			UINT32 iCandidate = Parallel::AtomicIncrement( (volatile INT32*) & miCandidateFreeSlot );

			// avoid overflow
			iCandidate = iCandidate % iBlockCount;

			UINT32 iFree = maInfos[ iCandidate ];

			if( 1 == iFree )
			{
				// ... try to take it
				if( 1 == Parallel::AtomicCompareAndSwap( (volatile INT32*) & maInfos[ iCandidate ], 0, 1 ) )
				{	
//					Parallel::MemoryBarrier();

					// useful info 
					miCurrentAllocCount.Increment();
					miTotalAllocCount.Increment();

					// okaaayy
					iFound = iCandidate;

					break;
				}
			}
			iTry++;
		}


		//UINT32 iCandidate = ( miCandidateFreeSlot % miBlockCount );

		//Parallel::MemoryBarrier(); 

		//UINT32 i = iCandidate;

		//while( i < miBlockCount + iCandidate )
		//{
		//	// stay in the bounds!
		//	int iSlot = i % miBlockCount;

		//	UINT32 iFree = maInfos[ iSlot ];
		//	
		//	Parallel::MemoryBarrier();

		//	// TODO : first increment miCandidateFreeSlot, then try to take the returned int - retry if failed

		//	// if free ...
		//	if( 1 == iFree )
		//	{
		//		// ... try to take it
		//		if( 1 == Parallel::AtomicCompareAndSwap( (volatile INT32*) & maInfos[ iSlot ], 0, 1 ) )
		//		{	
		//			iCandidate = miCandidateFreeSlot; 

		//			Parallel::MemoryBarrier();


		//			// try to update - no worries if it won't update, it simply means some other thread updated it as well, we don't care if it is not extra accurate
		//			Parallel::AtomicCompareAndSwap( (volatile INT32*)& miCandidateFreeSlot, ( iCandidate + 1 ) % miBlockCount , iCandidate );

		//			// useful info 
		//			miCurrentAllocCount.Increment();
		//			miTotalAllocCount.Increment();

		//			// okaaayy
		//			iFound = iSlot;

		//			break;
		//		}
		//	}

		//	i++;
		//}

		MB_ASSERT( 0xFFFFFFFF != iFound, "Memory Pool is too small\n" );


		return & maBlocks[ iFound * miBlockSize ];

	}

	//--------------------------------------------------------------------------------------------------------------------
	//--------------------------------------------------------------------------------------------------------------------
	void		Free( UBYTE* _pBlock )
	{
		// compute its slot from its address
		UINT32 iSlot = static_cast<UINT32>( _pBlock - maBlocks ) / miBlockSize;

		MB_ASSERT( 0 == maInfos[ iSlot ], "LockFreeMemoryPool Corruption\n" );

		// and write-release it :)
		maInfos[ iSlot ] = 1;
		Parallel::MemoryBarrier();

		// useful info 
		miCurrentAllocCount.Decrement();
	} 

	//--------------------------------------------------------------------------------------------------------------------
	//--------------------------------------------------------------------------------------------------------------------
	UINT32		GetTotalAllocationsCount( void ) const
	{
		return miTotalAllocCount.Get();
	}

	//--------------------------------------------------------------------------------------------------------------------
	//--------------------------------------------------------------------------------------------------------------------
	UINT32		GetAllocationsCount( void ) const
	{
		return miCurrentAllocCount.Get();
	}

	//--------------------------------------------------------------------------------------------------------------------
	//--------------------------------------------------------------------------------------------------------------------
	void		PolluteEvenIndices()
	{
		for( UINT32 i = 0; i < miBlockCount; i+=2 )
		{
			maInfos[ i ] = 0;
		}

		miCurrentAllocCount.Set( miBlockCount/2 );
		miTotalAllocCount.Set( miBlockCount/2 ); 
	}



private:
	UINT32							miBlockSize;
	UINT32							miBlockCount;
	volatile UINT32					miCandidateFreeSlot;
	Parallel::AtomicCounter			miCurrentAllocCount;
	Parallel::AtomicCounter			miTotalAllocCount; 

	UINT32*							maInfos;
	UBYTE*							maBlocks;

};


}// namespace Melting